package com.Offer;

import java.util.ArrayList;
import java.util.Arrays;

/*
    面试题40：最小的K个数
    题目描述：输入 n 个整数，找出其中最小的 K 个数。
    例如：4,5,1,6,2,7,3,8，最小的四个数为：1,2,3,4
 */
public class demo40 {
    public static void main(String[] args) {
        int[] input = {4,5,1,6,2,7,3,8};
        int[] ints = GetLeastNumbers_Solution(input, 4);
        for (int a : ints){
            System.out.print(a+" ");
        }

    }

    //方法一，基于快速排序的Position方法，得到k的位置，然后前面的数就都出来了，不好的地方在于会修改数组的位置
    public static int[] GetLeastNumbers_Solution(int[] input,int k){
        if(input == null || input.length == 0){
            return null;
        }
        int temp =position(input,0,input.length-1);
        while(temp != k-1){
            if(temp > k-1){
                temp = position(input,0,temp-1);
            }else{
                temp = position(input,temp+1,input.length-1);
            }
        }
        return Arrays.copyOfRange(input,0,temp+1);
    }

    public static int position(int[] input,int start,int end){
        int temp = input[start];
        while(start < end){
            while(start < end && input[end] >= temp){
                end--;
            }
            input[start] = input[end];
            while(start < end && input[start] <= temp){
                start++;
            }
            input[end] = input[start];
        }
        input[start] = temp;
        return start;
    }

    //-------------------------------------------------------------------------
    public ArrayList<Integer> GetLeastNumbers_Solution2(int[] input,int k){
        ArrayList<Integer> list = new ArrayList<>();




        return list;
    }

}
